package com.moyoutian.leetcode.jianzhi;

/**
 * 剑指 Offer 24. 反转链表
 * <p>
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 * <p>
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL
 * <p>
 * 输出: 5->4->3->2->1->NULL
 * <p>
 * <p>
 * 限制：
 * <p>
 * <p>
 * 0 <= 节点个数 <= 5000
 * <p>
 * <p>
 * <p>
 * 注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/
 * <p>
 * 通过次数296,784提交次数399,629
 */
public class Demo24 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }


    public static void main(String[] args) {
        ListNode listNode = new ListNode(0);
        ListNode head = listNode;
        for (int i = 1; i < 10; i++) {
            listNode.next = new ListNode(i);
            listNode = listNode.next;
        }
        //反转链表
        ListNode reverseList = reverseList(head);

        ListNode temp = reverseList;
        while (temp != null) {
            System.out.print(temp.val + " ,");
            temp = temp.next;
        }
    }


    /**
     * 反转链表
     *
     * @param head 头结点
     * @return 新的头结点
     */
    public static ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        //新的头结点
        ListNode newHeadNode = head;
        //新待加入结点
        ListNode node = head.next;
        //断开循环
        newHeadNode.next = null;
        while (node != null) {
            //临时记录
            ListNode nextNode = node.next;
            //将新加入结点指向原来的头结点
            node.next = newHeadNode;
            //设置头结点
            newHeadNode = node;
            node = nextNode;
        }
        return newHeadNode;
    }

}
